import java.util.Scanner;

public class Test {
    public int mySqrt(int x) {
        //找出x的平方根
        if(x<1)return 0;
        long left=1,right=x;
        while(left<right){
            long mid=left+(right-left+1)/2;
            if(mid*mid<=x)left=mid;
            else right=mid-1;
        }
        return (int) left;
    }

    public int searchInsert(int[] nums, int target) {
        //搜索插入位置(target在数组中出现的位置，若不存在就返回应该插入的位置)
        int left=0,right=nums.length-1;
        while(left<right){
            int mid=left+(right-left+1)/2;
            if(nums[mid]<=target)left=mid;
            else right=mid-1;
        }
        if(nums[left]<target)return left+1;//处理特殊情况
        return left;
    }


    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.println("第一题");
        System.out.println("请输入要找出对应平方根的值:");
        int x=in.nextInt();
        System.out.println(x+"的算术平方根为："+new Test().mySqrt(x));
        System.out.println("第二题");
        int[] arr1={1,3,5,6};
        System.out.println("答案一："+new Test().searchInsert(arr1, 3));
        System.out.println("答案二："+new Test().searchInsert(arr1, 5));
    }
}
